package countNegatives;

public class Solution {
    public int countNegatives(int[][] grid) {
        // 思路 从后往前遍历
//        int m = grid.length;
//        int n = grid[0].length;
//        int startJ = n-1;
//        int count = 0;
//        for (int i = 0; i < grid.length; i++) {
//            while (startJ>=0&&grid[i][startJ]<0){
//                startJ--;
//            }
//            count+=(n-(startJ+1));
//        }
//        return count;
            // 1 1 -1 -2
            // 1 -1 -2 -3
            // 1

        // 二分查找
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;
        for (int i = 0; i < m; i++) {
            int l = 0;
            int r = n-1;
            // 找到第一个小于0的数的位置
            int pos = n;
            while (l<=r){
                int mid = (l+r)/2;
                if(grid[i][mid]>=0){
                    l = mid+1;
                }else {
                    r = mid-1;
                    pos = mid;
                }
            }
            ans+=(n-pos);
        }
        return ans;
    }
}
